\section{Einführung} \label{sec:einfuehrung}
In dieser Seminararbeit wird das Thema Parallelisierung etwas genauer beleuchtet. Zu Beginn wird ein kurzer Überblick über die Bedeutung und Wichtigkeit von Parallelisierung im Allgemeinen gegeben und danach wird sich der Parallelisierung des bekannten Komprimierungsprogramms GZIP gewidmet.

\subsection{Parallelisierung Allgemein}
Nur noch in sehr wenigen Bereich der Informatik bzw. der Softwareentwicklung kommt man an den Themen Parallelisierung, Multi-Threading, Nebenläufigkeit etc. vorbei. Dabei steckt im Grunde hinter all diesen Ausprägungen das selbe Ziel, die gleichzeitige Bearbeitung unterschiedlicher Prozessoranweisungen. \\ 
Gerade einmal vor etwas mehr als zehn Jahren wurde der erste Multi-Core Prozessor, der Power4 von IBM \cite{power4}, entwickelt. Zuvor war die parallele Ausführung von Anweisungen nur durch mehrere Prozessoren realisierbar. Seither spielt die Parallelisierung von Software eine immer größere Rolle in der Informatik. Dieses Thema hat nochmals einen besonderen Aufschwung durch die Einführung der Multi-Core Prozessoren im Konsumentenmarkt erlebt. Heutzutage wird praktisch kein PC mehr ohne Multi-Core Prozessor gefertigt, selbst im embedded Bereich nimmt diese Technologie langsam ihren Einzug (siehe MSC8122 von Freescale \cite{msc8122}).\\
Nachdem die Multi-Core Technologie nun eine so wichtige Bedeutung hat, ist es nicht weiter verwunderlich, dass viele Bereiche der Informatik nun darauf reagieren müssen. Im Folgenden wird ausschließlich der Bereich Softwareentwicklung und dort genauer die Programmierung paralleler Anwendungen (in C) begutachtet.\\
Besonders präsent ist das Thema bei der Entwicklung von Oberflächen (GUIs). Hier ist es sehr wichtig eine flüssige Bedienbarkeit und einen performanten Eindruck der Anwendung zu gewährleisten. Dies wird meist durch multiple Threads realisiert, z.B. kümmern sich verschiedene Threads gleichzeitig um die Darstellung unterschiedlicher Fenster, während andere auf Benutzereingaben reagieren. Moderne Programmiersprachen bieten dem Entwickler hierbei bereits einige Unterstützung. Aber nicht nur im Bereich der Oberflächen-entwicklung ist Multi-Threading und Parallelisierung wichtig. Auch bei der Entwicklung der Business Logik und dem Verwalten von Daten kann die Parallelisierung viele Vorteile bringen. So können z.B. Berechnungen und Such-Abfragen auf Datenbanken parallelisiert werden.\\
Häufig bringt Parallelisierung also einen Performancegewinn. Es sei jedoch auch erwähnt, dass dies nicht immer der Fall ist. Jedes erstellen eines Threads oder eines eigenen Prozesses verbraucht Ressourcen. Eine sequenzielle Abarbeitung der einzelnen Tasks kann daher durchaus schneller sein als eine parallele. Manchmal bringt Parallelisierung auch erst nach einer bestimmten Anzahl an Durchläufen oder einer gewissen Datenmenge einen Geschwindigkeits\-vorteil. Weiterhin bedeutet Parallelisierung auch immer einen Mehraufwand in der Entwicklung, da hier besonders auf Abhängigkeiten geachtet werden muss und ggf. eine Synchronisation zwischen den einzelnen Threads nötig ist.\\

\subsection{GZIP} \label{subsec:gzip}
GZIP ist ein bekanntes und gerade in der Opern Source und Linux Welt, häufig genutztes Komprimierungsprogramm. Es handelt sich dabei um ein Open Source Projekt, dass von Jean-Loup Gailly und Mark Adler geschrieben wurde \cite{www_gzip}. Im Gegensatz zu dem eher in Windows eingesetzten ZIP-Programm, komprimiert GZIP ausschließlich einzelne Dateien. Daher wird es häufig in Kombination mit dem Packprogramm TAR verwendet, zu erkennen an der Dateiendung .tar.gz. Hierbei packt TAR einen Ordner oder mehrere Dateien zu einer einzigen Datei, die dann von GZIP komprimiert werden kann.\\
Der Komprimierungsalgorithmus von GZIP beruht auf einem Algorithmus zur sequenziellen Daten Komprimierung, der 1977 von Jacob Ziv und Abraham Lempel entworfen wurde \cite{alg_gzip}. Dieser Algorithmus wird im nächsten Kapitel genauer beschrieben.\\

\subsection{Vorgehensweise bei der Parallelisierung von C Programmen}
Dadurch, dass C bereits lange vor Multi-Core Prozessoren bzw. Multi-Threading existierte, ist es eher die Regel, dass C-Applikationen prozedural programmiert sind und somit sequenziell ausgeführt werden. Auch in prozeduralen C-Programmen kommt es jedoch oft vor, dass sich Teile des Programms unabhängig voneinander wiederholen. Am Beispiel von GZIP wäre das z.B. das Komprimieren mehrerer Files. Aus programmiertechnischer Sicht stellt dies ein und dieselbe Operation dar, welche mehrmals hintereinander ausgeführt wird. In der prozeduralen Entwicklung wird diese wiederholende Operation oft durch den Einbau von Schleifen realisiert, welche die Operationen nacheinander ausführen. Sind diese Operationen jedoch unabhängig voneinander und spielt die Reihenfolge in der diese fertig werden keine Rolle, kann man an dieser Stelle die Applikation parallelisieren und somit die Vorteile von Multi-Threading ausnutzen.\\
Wurde nun so eine Parallelisierungsmöglichkeit im C-Programm gefunden, muss das Programm meist umstrukturiert werden. Das heißt, der Programm-Teil, der parallel ausgeführt werden soll, sollte, wenn es sich vermeiden lässt, keinerlei Abhängigkeiten zu anderen Threads haben. Ist diese Isolierung nicht vollends möglich, können Resourcen die von mehreren Threads benötigt werden z.B. über Mutexes\footnote{Mutex steht für MutualExclusion} kurzzeitig für andere gesperrt werden. Benötigt nun ein Thread eine dieser geteilten Resources muss er einen Lock (Sperre) auf diese setzen, damit es während der Dauer dieses Locks keinem anderen Thread möglich ist, diese Resource zu verändern. Nachdem der Thread die Resource nicht mehr benötigt, wird sie wieder freigegeben und steht den anderen Threads zur Verfügung. Neben Mutexes bietet C auch noch den Einsatz von Semaphoren, welche anstatt von Locks, einer Resource einen Zähler zuordnen. Erreicht dieser Zähler null, ist es nicht mehr möglich die Resource zu verändern, dh. der Thread muss warten, bis der Zähler wieder den Wert Eins bekommt.
\newline
\newline

\subsubsection{Parallelisierungsvarianten in C}$\;$ \\
Die Programmiersprache C unterstützt seit der Version C11 Multi-Threading und erlaubt somit die Entwicklung parallel 
operierender Programme. Es gibt nun mehrere Varianten um ein C-Programm zu parallelisieren. Zwei Beispiele um dies zu erreichen werden in folgenden beschrieben. \\\\
\textbf{POSIX Threads} \label{textbf:LZ77} \\
Um POSIX\footnote{POSIX ist ein Akronym für Portable Operating System Interface} Threading in C verwenden zu können, muss die Bibliothek \textit{pthread} (kurz für POSIX Threads) zum Programm hinzugefügt werden. Außerdem muss der Compileraufruf um den Parameter \textit{-pthread} erweitert werden. Der Einsatz von \textit{pthread} in einem C-Programm wird am Beispiel Algorithmus \ref{alg:posix} gezeigt.\cite{posixHelloWorld}
\begin{lstlisting}[caption="Hello World" Beispiel (POSIX Threading in C) \cite{posixHelloWorld},label=alg:posix]
#include <pthread.h>
#include <stdio.h> 
#include <stdlib.h>
#define NUM_THREADS  5

void *PrintHello(void *threadid) {
  long tid;
  tid = (long)threadid;
  printf("Hello World! It's me, thread #%ld!\n", tid);
  pthread_exit(NULL);
}
int main(int argc, char *argv[]) {
  pthread_t threads[NUM_THREADS];
  int rc;
  long t;
  for(t=0;t<NUM_THREADS;t++){
    printf("In main: creating thread %ld\n", t);
    rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);
    if (rc){
      printf("ERROR; return code from pthread_create() is %d\n", rc);
      exit(-1);
    }
  }
  pthread_exit(NULL);
}
\end{lstlisting} 
$\;$ \\
In diesem Hello World  Beispiel werden Fünf Threads mit Hilfe von \textit{pthread\_create(...)} erstellt, welche jeweils die Methode \textit{PrintHello(...)} ausführen und im Zuge dessen ihre Thread ID auf der Konsole ausgeben. Ein Beispiel Output eines Durchlaufs für einen Thread wäre: \textit{\grqq In main: creating thread 0 \textbackslash n Hello World! It's me, thread \#0!\grqq}.
\clearpage
\noindent
\textbf{OpenMP} \label{textbf:openMP} \\
Bei OpenMP handelt es sich nicht nur um eine Library, wie bei POSIX, sondern um ein Application Programming Interface (API), welches die Sprachen FORTRAN, C und C++ um Anweisungen erweitert. Die Programm-Teile, welche parallel ausgeführt werden sollen, müssen definiert werden, damit OpenMP dann diese Teile automatisch parallelisieren kann. Die sehr simple Anweisung \textit{\#pragma omp parallel} signalisiert OpenMP z.B., dass die folgende Operation in multiplen Threads ausgeführt werden soll. Neben diesen Anweisungen im C-Programm muss auch hier zusätzlich der Compileraufruf um einen Parameter ergänzt werden, nämlich \textit{-fopenmp}. Der Einsatz von OpenMP in einem C-Programm wird am Beispiel Algorithmus \ref{alg:helloOpenMP} gezeigt. 
\lstset{caption={"Hello World" Beispiel (OpenMP in C) \cite{posixHelloWorld}}, label=alg:helloOpenMP}
\begin{lstlisting}
#include <stdio.h>
 
int main(void) {
  #pragma omp parallel
    printf("Hello, world.\n");
  return 0;
}
\end{lstlisting}
$\;$ \\
Bei einem Computer mit 2 Cores und 2 Threads würde das Ausführen dieses Programms folgenden Output erzeugen: \textit{\grqq Hello, world. \textbackslash n Hello, world.\grqq}. \\
Dieses sehr simple Hello World Beispiel soll zeigen, wie man den zu parallelisierenden Bereich in einem C-Programm definieren muss, damit OpenMP das Programm automatisch parallelisieren kann. Diese automatische Parallelisierung ist ein Java Programm, welches das zu compilierende C-Programm vor dem Compilieren so umschreibt, dass es parallel ausgeführt werden kann. OpenMP setzt dabei u.a. die POSIX pthread Bibliothek ein. \cite{openMPArticle} \\\\
%TODO Fork
%\textbf{Fork} \label{textbf:fork} \\
%text \\
\newline
\newpage







